/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-07-11
 * Time: 23:19
 */

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    public ListNode sortList(ListNode head) {
        if(head==null) return head;
        //求链表的长度
        ListNode tmp = head;
        int cnt = 0;
        while(tmp!=null){
            cnt++;
            tmp = tmp.next;
        }
        ListNode dummyHead = new ListNode(-1,head);
        for(int gap =1 ;gap<cnt;gap*=2){
            ListNode prev = dummyHead;
            ListNode cur = dummyHead.next;
            while(cur!=null){
                ListNode head1 = cur;
                for(int i=1;i<gap&&cur.next!=null;++i){
                    cur = cur.next;
                }
                ListNode head2 = cur.next;
                cur.next = null;
                cur = head2;
                for(int i =1;i<gap&&cur!=null&&cur.next!=null;++i){
                    cur = cur.next;
                }
                ListNode next = null;
                if(cur!=null){
                    next = cur.next;
                    cur.next = null;
                }
                ListNode megerd = merge(head1,head2);
                prev.next = megerd;
                while(prev.next !=null){
                    prev = prev.next;
                }
                cur = next;
            }
        }
        return dummyHead.next;
    }

    public ListNode merge(ListNode l1,ListNode l2){
        ListNode dummyHead = new ListNode(-1);
        ListNode prev = dummyHead;
        while(l1!=null&&l2!=null){
            if(l1.val<l2.val){
                prev.next = l1;
                l1 = l1.next;
            }else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }
        if(l1!=null){
            prev.next = l1;
        }else if(l2!=null){
            prev.next = l2;
        }
        return dummyHead.next;
    }

}

class Solution1 {
    public void reorderList(ListNode head) {
        if(head==null) return;
        //找到链表中间结点的前一个节点
        ListNode slow = head;
        ListNode fast = head.next;
        while(fast!=null&&fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        //此时slow就是上一个链表的尾巴
        ListNode tmp = slow.next;
        slow.next = null;
        //然后将tmp这个链表开始进行反转
        ListNode newhead = reverse(tmp);
        //开始进行合并两条链表
        ListNode dummyHead = new ListNode(-1);
        ListNode prev = dummyHead;
        while(head!=null&&newhead!=null){
            prev.next = head;
            head = head.next;
            prev = prev.next;
            prev.next = newhead;
            if(newhead!=null)
                newhead = newhead.next;
            prev = prev.next;
        }
        if(head!=null){
            prev.next = head;
        }else {
            prev.next = newhead;
        }
        head =dummyHead.next;
    }

    public ListNode reverse(ListNode head){
        if(head==null) return head;
        ListNode cur = head;
        ListNode prev = null;
        while(cur!=null){
            ListNode curNext = cur.next;
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }
        return prev;
    }
}

class Solution2 {
    public ListNode insertionSortList(ListNode head) {
        if(head==null) return head;
        ListNode dummyHead = new ListNode(-1,head);
        ListNode sortedLast = head;//将第一个节点看做是有序的
        ListNode cur = head.next;//从第二个节点开始插入到前面让其有序
        while(cur!=null){
            if(sortedLast.val<=cur.val){//证明是有序的
                sortedLast= sortedLast.next;
            }else {
                //证明没有序,我们要从头找位置,cur要插入到那个地方
                ListNode prev = dummyHead;//prev是cur的前一个节点
                //只要prev的下一个节点比cur大那就证明prev的下一个就应该插入cur
                while(prev.next.val<=cur.val){
                    prev = prev.next;
                }
                //此时prev的下一个节点的值大于cur节点的值,所以要把cur插入到prev的后面
                sortedLast.next = cur.next;
                cur.next = prev.next;
                prev.next = cur;
            }
            //每次cur都是待插入的元素要在sortedLast的下一个
            cur = sortedLast.next;
        }
        return dummyHead.next;
    }
}




public class TestDemo {





}
